home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 July: Mac OS SDK / Dev.CD Jul 96 SDK / Dev.CD Jul 96 SDK1.toast / Development Kits (Disc 1) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Utilities / HshTbl.c < prev    next >
Encoding:
Text File  |  1996-04-22  |  26.7 KB  |  723 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        HshTbl.c
  3.  
  4.     Contains:    AEHshTbl from C version of Apple Event Manager.
  5.  
  6.     Owned by:    Jon Pugh
  7.  
  8.     Copyright:    © 1993 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     
  11. */
  12.  
  13.  
  14. //#ifndef AEMDEFINES_H
  15. //#include "AEMDefines.h"
  16. //#endif
  17.  
  18. #include <errors.h>
  19.  
  20. #ifndef __HshTbl__
  21. #include "HshTbl.h"
  22. #endif
  23.  
  24. //#ifndef __AEUtil__
  25. //#include "AEUtil.h"
  26. //#endif
  27.  
  28. //#ifndef __AEDFWrpp__
  29. //#include "AEDFWrpp.h"
  30. //#endif
  31.  
  32. #ifndef __MEMORY__
  33. #include <Memory.h>
  34. #endif
  35.  
  36. #ifndef __STRING_H
  37. #include <string.h>        // for memcpy
  38. #endif
  39.  
  40. #ifndef __TOOLUTILS__
  41. #include <ToolUtils.h>
  42. #endif
  43.  
  44. /* Internal Details
  45.  ---------------- 
  46.                                                                       The value field when called from AEM
  47.                                                                       
  48.                                                                                                      'IsSpecial'
  49.                                                                                 
  50.     Hash Table Entry                                                                                   |
  51.                                                                                                       |
  52.       hashed key    | Handle to list|    complete key data here     |-- user's value, variable size --|-----|
  53.     +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+-v-+---+
  54.     |      Tag      |    CollList   |      Key1     |      Key2     |  therefcon    :    procptr    :flag   |--> more entries              
  55.     +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  56.  
  57.     NOTE: This layout is fixed in this implementation. Calling NewHashTable with values in KeySize 
  58.           that do not conform to this description will not have the expected results. However, the
  59.           value can be a variable size.
  60.           
  61.     1) Each entry may have a collision list associated with it. This is simply a linked list of
  62.     Table Entries, which only exists if more than one key hashes to the same Tag.
  63.     
  64.     2) If the intial entry is emptied by RemoveKeyEntry, and there is a list, the DATA of the first
  65.     list entry is moved into the table, the Handle that originally pointed to that list entry is
  66.     disposed.
  67.     
  68.     3) Removal of a list entry is simply implemented by handle adjustment, and disposal of the original
  69.     handle.
  70.     
  71.     4) Addition of a list entry is always at the head of the list, stack fashion.
  72.     
  73.     5) FindAnEntry notes, implied from the foregoing :
  74.       a) If there is a collision list, a pointer to an available slot will NEVER be returned
  75.          by FindAnEntry (kFoundKey or kNoSlot are the only returns in this case).
  76.       b) Two handles are also returned : 1 references the entry itself, the other references the entry
  77.          preceding it in the list.  If the current entry is the intial table entry, both are null.
  78.          Similarly, if the return is kNoSlot, both handles are null. If the entry is the first
  79.          in the list, the handle to the previous entry is null.
  80. */
  81.          /*
  82.          *    The header of a hash table 
  83.          *
  84.          */
  85. #if defined(powerc) || defined (__powerc)
  86. #pragma options align=mac68k
  87. #endif
  88. typedef struct TableInfoRec {
  89.          long    HashMask,                 // Long mask to select the offset bits - set to KeySize -1.
  90.                  HashTableSize,            // physical size of the table.
  91.                  HashNumUsed,             // not used in this implementation - number of entries in use
  92.                  HashEntrySize,            // size of an entry.
  93.                  HashNumExtra;            // not used  - # extra entries at end of table 
  94.          short    HashMagnitude,            // not used  - # bits in hash index
  95.                  HashFullPercent,        // not used  - grow table when more than this percent used
  96.                    HashPercentUsed,        // not used  - current percent used
  97.                  HValueOffset,            //offset to the value within an entry.
  98.                  HashKeySize,            //size of a key
  99.                  HashValueSize;            //size of a data value.
  100.          Boolean InSysHeap;                // is it in the system memory
  101.      }TableInfoRec,  * TableInfoPtr,  ** TableInfoHdl;
  102. #if defined(powerc) || defined(__powerc)
  103. #pragma options align=reset
  104. #endif
  105.  
  106.      
  107. #define HeaderSize    sizeof(TableInfoRec)
  108.          /*
  109.          *
  110.          *   An Entry in the Table
  111.          *
  112.          */
  113. typedef struct TableEntry  * TableEntryPtr;
  114. typedef TableEntryPtr  * TableEntryHdl;
  115.  
  116. #if defined(powerc) || defined (__powerc)
  117. #pragma options align=mac68k
  118. #endif
  119. typedef struct TableEntry {
  120.             long            Tag;
  121.             TableEntryHdl    CollList;     // if there are collisions, search this list
  122.             KeyRec            theKey;
  123.             handlerRec        theValue;
  124.         }TableEntry;
  125.  
  126. #if defined(powerc) || defined(__powerc)
  127. #pragma options align=reset
  128. #endif
  129.        /*
  130.        *   Defines
  131.        *
  132.        */
  133. #define BitsInLong (sizeof(long) * 8)  // used in InLineHash (c version)
  134.  
  135. #define  kEmptySlot    0L
  136.        /* 1 of these 3 will be returned by FindAnEntry */
  137. #define kFoundKey     0        //found theKey, am returning a pointer to its' slot
  138. #define kFoundSlot     1        //didn't find theKey; returning a pointer to available slot
  139. #define kNoSlot         -1        //didn't find theKey; returning a pointer to CollList field of TableEntry
  140.  
  141. #define KeysNotEqual(x,y) ((x.firstKey != y.firstKey) || (x.secondKey != y.secondKey) )
  142.  
  143.  
  144. /* Note that a collision indicates that there are 2(or more) entries xharing a Tag(hash) value, with different
  145.    key values.
  146. */
  147. #define collision(x) ((currEntry->Tag != x) \
  148.                     || (KeysNotEqual((*(KeyRecPtr)srchKey),(*(KeyRecPtr)&currEntry->theKey))))
  149.  
  150. //------------------------ Prototypes of internal routines ---------------------------------
  151.  
  152. unsigned long InLineHash(KeyPtr srchKey);  // for PPC,  in C; 68K in assembler
  153.                   
  154. TableEntryPtr PointInTable(HHand Hash,KeyPtr srchKey, long  * theHashValue);
  155.  
  156. OSErr SrchCollLst(TableEntryHdl theList, long theTag, KeyPtr srchKey, HEntryPtr  * theEntry,
  157.                   TableEntryHdl  * currHdl, TableEntryHdl  * PredHdl);
  158.  
  159. OSErr FindAnEntry(KeyPtr srchKey, HEntryPtr  * theEntry, HHand Hash,
  160.                  TableEntryHdl  * theHdl, TableEntryHdl  * preHdl);
  161.  
  162. //--------------------------- internal routines -----------------------------------------------
  163.  
  164. //  C version of InLineHash
  165.  
  166. unsigned long int InLineHash(KeyPtr theKey)
  167. {
  168.  
  169.    unsigned long  int * ulongPtr = (unsigned long  int *)theKey;
  170.    unsigned long  int  workingLong = *ulongPtr;      // a key is 2 longs, we deal w/ them one at a time
  171.  
  172.  // Rotate left by 5
  173.    workingLong = (workingLong >> 5) | (workingLong << (BitsInLong - 5)) + *ulongPtr;
  174.    workingLong = (workingLong >> 5) | (workingLong << (BitsInLong - 5)) + *ulongPtr;
  175.    workingLong = (workingLong >> 5) | (workingLong << (BitsInLong - 5)) + *(ulongPtr++);
  176.    
  177.    workingLong += *ulongPtr;
  178.    
  179.  // Rotate right by 5
  180.  
  181.    workingLong = (workingLong << 5) | (workingLong >> (BitsInLong - 5)) + *ulongPtr;
  182.    workingLong = (workingLong << 5) | (workingLong >> (BitsInLong - 5)) + *ulongPtr;
  183.    workingLong = (workingLong << 5) | (workingLong >> (BitsInLong - 5)) + *ulongPtr;
  184.  
  185. //   Multiply least significant word by 0xB33D, and store the product as long
  186.    workingLong = (unsigned long  int)(LoWord(workingLong) * (unsigned short int)0XB33D);
  187.  
  188. //   set the most significant bit - insures no Tag will ever = 0
  189.     BitSet((char  *) &workingLong,31L);
  190.     return workingLong;
  191.   }
  192.  
  193. // -------------------------------------------------------------------------------------------
  194.  
  195.  
  196.            /*
  197.             PointInTable    Derive a pointer to a table entry
  198.             -----------
  199.                Entry:    Hash    - Pointer to Handle to the hash table
  200.                         srchKey  - The key to be indexed
  201.                         
  202.                Exit:    returns - Pointer to the table entry , and :
  203.                            theHashValue    - set to the hashed value of srchKey
  204.            */
  205. TableEntryPtr PointInTable(HHand Hash,KeyPtr srchKey, long  * theHashValue)
  206.    { long        theIndex;
  207.      void  * hshDeRefPtr;
  208.      if (Hash != NULL)
  209.        {
  210.          hshDeRefPtr = DEREF_OF(Hash);
  211.          *theHashValue = InLineHash(srchKey);                 // compute the hash value for the key.
  212.          theIndex = (*theHashValue & ((TableInfoPtr)hshDeRefPtr)->HashMask);    // mask down to the index bits.
  213.          theIndex *= ((TableInfoPtr)hshDeRefPtr)->HashEntrySize;                // multiply by the entry size
  214.          CLEAR_REF_OF(Hash);
  215.          return (TableEntryPtr)((Ptr)hshDeRefPtr + HeaderSize + theIndex);
  216.        }
  217.      else
  218.         return NULL;
  219.    }    /* PointInTable */
  220. //-------------------------------------------------------------------------------------------
  221.            /*
  222.             SrchCollLst        Search for the matching entry in the collision list.
  223.             -----------
  224.                Entry:    theList - Handle to the collision list
  225.                         theTag  - Hashed value to search for
  226.                         srchKey  - The key to search for
  227.                         
  228.                Exit:    result is 1 of :
  229.                            kFoundKey    found srchKey, am returning a pointer to its' slot
  230.                            kNoSlot        didn't find srchKey; theEntry is undefined
  231.                         theEntry -  pointer as indicated above
  232.                         currHdl  -  Handle associated with theEntry
  233.                         PredHdl  -  Handle to entry before theEntry
  234.            */
  235. OSErr SrchCollLst(TableEntryHdl theList, long theTag, KeyPtr srchKey, HEntryPtr  * theEntry,
  236.                   TableEntryHdl  * currHdl, TableEntryHdl  * PredHdl)
  237.    {
  238.      TableEntryPtr  currEntry;
  239.      OSErr    theReturn = kNoSlot;
  240.  
  241.      *currHdl  = theList;
  242.      currEntry  = (TableEntryPtr)DEREF_OF(*currHdl);
  243.      if (currEntry != NULL)
  244.       {
  245.         theReturn = kFoundKey;     //let's be optimistic
  246.         while (collision(theTag))
  247.           {
  248.             if (currEntry->CollList == NULL)
  249.               {
  250.                 theReturn = kNoSlot;        // forget it
  251.                  break;
  252.                }
  253.             else
  254.              {
  255.               CLEAR_REF_OF(*currHdl);       //unlock the last one used
  256.               *PredHdl    = *currHdl;  // retain this handle as predecessor
  257.               *currHdl    = currEntry->CollList;
  258.               currEntry  = (TableEntryPtr)DEREF_OF(*currHdl);
  259.              }
  260.            }        /* while (collision(theTag)) */
  261.         if (theReturn != kNoSlot)            //MUST, therefore, be kFoundKey
  262.            *theEntry = (HEntryPtr)currEntry;
  263.         }            /* (currEntry != NULL) */
  264.      CLEAR_REF_OF(*currHdl);       //drop deref the last one used
  265.      return theReturn;
  266.    }    /* SrchCollLst */
  267.    
  268. // ---------------------------------------------------------------------------------
  269.  
  270. // Dispose the hash table, the only tricky stuff is to get rid of all the collision lists first
  271.  
  272. OSErr  DisposeHashTable(HHand *Hash, MemProcs MemHooks)
  273.  
  274.    {
  275.            TableInfoPtr        tblDeRefPtr;
  276.            TableEntryPtr     tblEntryPtr, tableEnd;
  277.            TableEntryHdl    collisionList, tempEntry;
  278.  
  279.  
  280.         if (*Hash != NULL)
  281.             {
  282.             HLOCK(*Hash);
  283.             tblDeRefPtr = (TableInfoPtr)DEREF_OF(*Hash);
  284.             tblEntryPtr = (TableEntryPtr)((Ptr)(tblDeRefPtr) + sizeof(TableInfoRec)); // start search here
  285.             tableEnd = (TableEntryPtr)((Ptr)(tblDeRefPtr) + tblDeRefPtr->HashTableSize); // and end search here
  286.             while (tblEntryPtr < tableEnd)
  287.                 { // go through all the entry and look for the collision list
  288.                 collisionList=tblEntryPtr->CollList;
  289.                 while (collisionList != NULL)
  290.                     {
  291.                     tempEntry = ((TableEntryPtr)DEREF_OF(collisionList))->CollList; // next item in the collision list
  292.                     CLEAR_REF_OF(collisionList);
  293.                     DISPOSEHANDLE (collisionList);
  294.                     collisionList = tempEntry; // continue with next item in the collision list
  295.                     }
  296.                 // now go and look at the next entery
  297.                 tblEntryPtr = (TableEntryPtr)((Ptr)tblEntryPtr + tblDeRefPtr->HashEntrySize);
  298.                 }
  299.             HUNLOCK(*Hash);
  300.             DISPOSEHANDLE (*Hash);
  301.             *Hash = NULL; // After we have disposed it, table does not exist
  302.             }
  303.         return noErr;
  304.     }    // DisposeHashTable
  305. //-------------------------------------------------------------------------------------------
  306.  
  307.  
  308.            /*
  309.             FindAnEntry        Search for the matching entry.
  310.             -----------
  311.                Entry:    srchKey - Pointer to the Key.
  312.                         Hash - Pointer to HashTable handle
  313.                         
  314.                Exit:    return: 1 of :
  315.                            kFoundKey    found srchKey, am returning a pointer to its' slot
  316.                            kFoundSlot    didn't find srchKey; returning a pointer to available slot
  317.                            kNoSlot        didn't find srchKey; returning pointer to TableEntry
  318.                         theEntry -  pointer as indicated above
  319.                         theHdl   -  Handle associated with theEntry (NULL if initial table entry)
  320.                         PreHdl   -  Handle to entry before theEntry (NULL if table entry OR 1st list entry)
  321.            */
  322. OSErr FindAnEntry(KeyPtr srchKey, HEntryPtr  * theEntry,HHand Hash,
  323.                  TableEntryHdl  * theHdl, TableEntryHdl  * preHdl)
  324.   {
  325.      TableEntryPtr  currEntry, 
  326.                      startEntry; 
  327.      OSErr    theReturn;
  328.      long     theHashValue;
  329.            
  330.      currEntry = startEntry = PointInTable(Hash, srchKey, &theHashValue);
  331.      *theHdl   = *preHdl = NULL;           //No handle to the entry, nor it's list predecessor
  332.      theReturn = kFoundKey;             //let's be optimistic
  333.      if (currEntry->Tag == kEmptySlot)
  334.        theReturn = kFoundSlot;             //an available slot to use
  335.      else
  336.        if (collision(theHashValue))
  337.          if (currEntry->CollList == NULL)
  338.            theReturn = kNoSlot;
  339.          else
  340.            theReturn = SrchCollLst(currEntry->CollList,theHashValue, srchKey, (HEntryPtr  * )&currEntry,
  341.                                     theHdl, preHdl);
  342.  
  343.      if (theReturn == kNoSlot)    /* return the ptr to the TableEntry indicated by theIndex */
  344.        {
  345.         *theEntry = (HEntryPtr)startEntry;   /* point to the TableEntry */
  346.         *theHdl   = *preHdl = NULL;   //No handle to the entry, nor it's list predecessor
  347.         }
  348.      else
  349.         *theEntry = (HEntryPtr)currEntry;
  350.  
  351.      return theReturn;      // points to the correct one, a useable one, or CollList field of TableEntry
  352.   }    /* FindAnEntry */
  353. // ---------------------------------------------------------------------------------
  354.  
  355.  
  356. // ------------------------Externally-available Functions ---------------------------
  357.  
  358.          /*
  359.             GetKeyValue - Find the hashed entry.
  360.             -----------
  361.                Entry:    Hash        - the hash table to search
  362.                         Key            - Pointer to the Key.
  363.                         
  364.                Exit:    Returns an error if not found.
  365.                         Value - memory pointed to is filled with the Value field of the entry.
  366.          */
  367. OSErr  GetKeyValue(HHand Hash, MemProcs MemHooks,KeyPtr Key, HEntryPtr Value)
  368.    {
  369.         OSErr            theReturn;
  370.         HEntryPtr        theEntry;
  371.         Ptr                EntryVal;  //the value in the table entry
  372.         TableEntryHdl    dummy = NULL;
  373.         void  *        hshDeRefPtr;
  374.  
  375.         theReturn =  FindAnEntry(Key, &theEntry, Hash, &dummy, &dummy);
  376.         if (theReturn == kFoundKey)
  377.            {
  378.               theReturn = noErr;
  379.               hshDeRefPtr = (TableInfoPtr)DEREF_OF(Hash);
  380.                  EntryVal = (theEntry + ((TableInfoPtr)hshDeRefPtr)->HValueOffset);
  381.  
  382. /*
  383.               for (i = 0; i < ((TableInfoPtr)hshDeRefPtr)->HashValueSize; i++,((char  *)Value)++,EntryVal++)
  384.                  *Value = *EntryVal;
  385. */
  386.               memcpy((void *)Value, (void *)EntryVal, ((TableInfoPtr)hshDeRefPtr)->HashValueSize);
  387.              CLEAR_REF_OF(Hash);
  388.            }        /* (theReturn == kFoundKey) */
  389.         else
  390.            theReturn = ErrNotFound;
  391.  
  392.         return theReturn;
  393.    }        /* GetKeyValue */
  394. // ---------------------------------------------------------------------------------
  395.  
  396. /*
  397. CheckKey - Find the hashed entry.
  398. -----------
  399. Entry:    Hash    - the hash table to search
  400. Key    - Pointer to the Key.
  401.  
  402. Exit:    Returns an error if not found.
  403. Value - memory pointed to is filled with the Value field of the entry.
  404. */
  405. Boolean CheckKey(HHand Hash, MemProcs MemHooks, KeyPtr Key) 
  406. {
  407. HEntryPtr    theEntry;
  408. TableEntryHdl    dummy = NULL;
  409.  
  410. return ((FindAnEntry(Key, &theEntry, Hash, &dummy, &dummy)) == kFoundKey);
  411. }    /* CheckKey */
  412.  
  413. // --------------------------------------------------------------------------------- 
  414. // Get the index th entry from the hash table, the order we use here is we go through the table
  415. // and down the collison list if possible, so the order would be like 1, 2, 2a, 2b, 3, 4, 4a, 4b
  416. // where the alphabet subscript is on the collision list
  417.  
  418. // if we ever need to speed it up, a simple way is to remember the entry for the last GetIndexedEntry call
  419.  
  420.  
  421. OSErr  GetIndexedEntry(HHand Hash, MemProcs MemHooks, long Index, KeyPtr Key, HEntryPtr Value)
  422.  
  423.    {
  424.        OSErr            err;
  425.        long             itemsFound;
  426.        TableInfoPtr        tblDeRefPtr;
  427.        TableEntryPtr     tblEntryPtr, tableEnd;
  428.        TableEntryHdl    collisionList, tempEntry;
  429.        Ptr                aPtr;
  430.        
  431.         err = ErrEndOfTable; // assume we reach the end of the table
  432.         if (++Index <= 0) return err; // also change from 0 origin to 1 origin
  433.         itemsFound = 0; // we have found nothing yet
  434.         tblDeRefPtr = (TableInfoPtr)DEREF_OF(Hash);
  435.         tblEntryPtr = (TableEntryPtr)((Ptr)(tblDeRefPtr) + sizeof(TableInfoRec)); // start search here
  436.         tableEnd = (TableEntryPtr)((Ptr)(tblDeRefPtr) + tblDeRefPtr->HashTableSize); // and end search here
  437.         collisionList = NULL; // we are not in any collision yet
  438.         
  439.         while (tblEntryPtr < tableEnd)
  440.             {
  441.             if (collisionList != NULL)
  442.                 { // we are in the middle of marching through the collision list
  443.                 if (++itemsFound == Index)
  444.                     { // we found it in the collisionList, copy the key and value
  445.                     tblEntryPtr = (TableEntryPtr)DEREF_OF(collisionList);
  446.                     memcpy(Key, (Ptr)(&(tblEntryPtr->theKey)), tblDeRefPtr->HashKeySize);
  447.                     memcpy(Value, (Ptr)(tblEntryPtr)+tblDeRefPtr->HValueOffset, tblDeRefPtr->HashValueSize);
  448.                     CLEAR_REF_OF(collisionList);
  449.                     err = noErr;
  450.                     break;
  451.                     }
  452.                 else
  453.                     { // access the next item in the collision list
  454.                     tempEntry = ((TableEntryPtr)DEREF_OF(collisionList))->CollList;
  455.                     CLEAR_REF_OF(collisionList);
  456.                     collisionList = tempEntry;
  457.                     }
  458.                 }
  459.             else if (tblEntryPtr->Tag == kEmptySlot)
  460.                 /* tblEntryPtr++; // keep marching until we find an non-empty slot */
  461.                 tblEntryPtr = (TableEntryPtr)((Ptr)tblEntryPtr + tblDeRefPtr->HashEntrySize);   //will work even if TableEntry not same size as specified by struct
  462.             else
  463.                 { // we found another entry
  464.                 if (++itemsFound == Index)
  465.                     { 
  466.                     aPtr = (Ptr)&(tblEntryPtr->theKey);
  467.                     memcpy(Key, (Ptr)(&(tblEntryPtr->theKey)), tblDeRefPtr->HashKeySize);
  468.                     memcpy(Value, (Ptr)(tblEntryPtr)+tblDeRefPtr->HValueOffset, tblDeRefPtr->HashValueSize);
  469.                     err = noErr;
  470.                     break;
  471.                     }
  472.                 else
  473.                     {
  474.                     collisionList = tblEntryPtr->CollList; // we may march down the collision list next
  475.                     tblEntryPtr++;
  476.                     }
  477.                 }
  478.             }
  479.         CLEAR_REF_OF(Hash);
  480.         return err;
  481.     }
  482.             
  483.             
  484.         
  485.         
  486.  
  487. // ---------------------------------------------------------------------------------
  488.         /*
  489.              NewHashTable - Creates a new hash table and returns the handle.
  490.              -----------
  491.                Entry:    NumEntries        - Initial # of entries to establish
  492.                         KeySize,
  493.                         ValueSize   - Sizes for these fields
  494.                         SysHeap     - Should the System heap be used; if not, goes in App heap
  495.                Exit:    Returns an error if failure.
  496.                         Table - pointer to the handle to the hashtable.
  497.         */
  498. OSErr  NewHashTable(long NumEntries,short KeySize, short ValueSize,MemProcs MemHooks,
  499.                                     Boolean SysHeap, HHand  * Table)
  500.    {
  501.        long        TableSize;
  502.        OSErr    theReturn = noErr;
  503.        TableEntryPtr theEntry;
  504.        long i;
  505.        TableInfoPtr    tblDeRefPtr;
  506.        long        entrySize;
  507.        
  508.                                    //calculate the size of one entry, round up to even number
  509.        entrySize = (sizeof(long) + sizeof(TableEntryHdl) + KeySize + ValueSize + 1) & -2;
  510.                                 //calculate the table size, and add header size
  511.        TableSize = (NumEntries * entrySize) + HeaderSize;
  512.                                 // create the hash table.
  513.         if (SysHeap)     // don't store the handle in applications heap
  514.            *Table = NEWHANDLESYS(TableSize);
  515.         else                  // DO store the handle in an app's AppRec
  516.            *Table = NEWHANDLE(TableSize);
  517.                                 // Set up the header with all of our information.
  518.         if (*Table != NULL)
  519.           {
  520.            tblDeRefPtr =(TableInfoPtr)DEREF_OF(*Table);
  521.            tblDeRefPtr->HashMask        = NumEntries-1;
  522.            tblDeRefPtr->HashTableSize    = TableSize;
  523.            tblDeRefPtr->HashNumUsed        = 0;                  //not used in this implementation
  524.            tblDeRefPtr->HashEntrySize    = entrySize; // hash + collision + key + value
  525.            tblDeRefPtr->HashNumExtra    = 0;                  //not used in this implementation
  526.            tblDeRefPtr->HashMagnitude    = 0;                  //not used in this implementation
  527.            tblDeRefPtr->HashFullPercent    = 0;              //not used in this implementation
  528.            tblDeRefPtr->HashPercentUsed    = 0;              //not used in this implementation
  529.            tblDeRefPtr->HValueOffset    = sizeof(long) + sizeof(TableEntryHdl) + KeySize;  //the Tag + collison + theKey
  530.            tblDeRefPtr->HashKeySize        = KeySize;      // This BETTER be sizeof(KeyRec)
  531.            tblDeRefPtr->HashValueSize    = ValueSize;    // This BETTER be >= sizeof(handlerRec)
  532.            tblDeRefPtr->InSysHeap        = SysHeap;        // added so we don't need param in ReplaceEntry etc
  533.                             
  534.            theEntry = (TableEntryPtr)((Ptr)tblDeRefPtr + HeaderSize);  //point to first actual entry
  535.            for (i = 0; i < NumEntries; i++, theEntry=(TableEntryPtr)((Ptr)theEntry+entrySize))
  536.              {
  537.                 theEntry->Tag                                        = kEmptySlot;
  538.                 theEntry->CollList                                      = NULL;
  539.         /* Somewhat bizarre initialization values used for ease of debugging */
  540.                 if (KeySize >= sizeof(KeyRec))
  541.                     { // only do this is the key size is big enough to do it
  542.                     (*(KeyRecPtr)&(theEntry->theKey)).firstKey         = 0x0FFFFFFFF;
  543.                     (*(KeyRecPtr)&(theEntry->theKey)).secondKey         = 0x0AAAAAAAA;
  544.                     }
  545.                 if (ValueSize >= sizeof(handlerRec))
  546.                     { // only do this is the value size is big enough to do it
  547.                     (*(handlerRec *)&(theEntry->theValue)).theRefCon = 0x0BBBBBBBB;
  548.                     (*(handlerRec *)&(theEntry->theValue)).theProc     = (UniversalProcPtr) 0x0CCCCCCCC;
  549.                     (*(handlerRec *)&(theEntry->theValue)).IsSpecial = false;
  550.                     }
  551.              }    /* for */
  552.            CLEAR_REF_OF(*Table);
  553.           }          /* (*Table != NULL) */
  554.         else
  555.           theReturn = ErrNoHashTable;
  556.           
  557.       return theReturn;
  558.    }    /* NewHashTable */
  559.  
  560. // ---------------------------------------------------------------------------------
  561.         /*
  562.              RemoveKeyEntry - Returns an error if entry not found.
  563.              --------------
  564.                Entry:    Hash        - the hash table to search
  565.                         Key            - Pointer to the Key.
  566.                         
  567.                Exit:    Returns an error if not found.
  568.         */
  569. OSErr  RemoveKeyEntry(HHand Hash, MemProcs MemHooks,KeyPtr Key)
  570.    {
  571.         OSErr            theReturn = noErr;
  572.         long            dummy;
  573.         HEntryPtr        theEntry,
  574.                          tblEntry;
  575.         register short    i;
  576.         TableEntryHdl      theHdl,
  577.                            preHdl;
  578.         TableEntryPtr   theHdlDeRefPtr;
  579.         TableEntryPtr   preHdlDeRefPtr;
  580.         TableEntryPtr   lstDeRefPtr;
  581.         
  582.         TableInfoPtr    tableDeRefPtr;
  583.         long            entrySize;
  584.         Boolean            InSys;
  585.         Ptr                entryChars;
  586.  
  587.         tableDeRefPtr = (TableInfoPtr)DEREF_OF(Hash);
  588.         entrySize = tableDeRefPtr->HashEntrySize;
  589.         InSys = tableDeRefPtr->InSysHeap;
  590.         CLEAR_REF_OF(Hash);
  591.  
  592.         if (FindAnEntry(Key, &theEntry, Hash, &theHdl, &preHdl) == kFoundKey)
  593.            if (theHdl == NULL)             // this is the initial table entry
  594.               {    
  595.                  if (((TableEntryPtr)theEntry)->CollList != NULL)
  596.                     {                     // There's a collision list, move values from it's 1st entry              
  597.                       lstDeRefPtr = (TableEntryPtr)DEREF_OF(((TableEntryPtr)theEntry)->CollList);
  598.                       
  599.  
  600. /*                      for (i = 0; i < entrySize; i++, ((char  *)theEntry)++,((Ptr)lstDeRefPtr)++ )
  601.                          *((Ptr)theEntry) = *((Ptr)lstDeRefPtr);
  602. */
  603.                       memcpy((void *)theEntry, (void *)lstDeRefPtr, entrySize);
  604.  
  605. #if WINDOWS /*  11/6   RETAIN TILL DECIDE WHAT TO DO ABOUT SYSTEM HEAP */
  606.                         // don't want to us myGlobalFree if this is in the system heap
  607.                      if(InSys)
  608.                        {
  609.                          HUNLOCK(((TableEntryPtr)theEntry)->CollList);
  610.                          GlobalFree((HGLOBAL)((TableEntryPtr)theEntry)->CollList);
  611.                        }
  612.                      else
  613. #endif
  614.                       DISPOSEHANDLE (((TableEntryPtr)theEntry)->CollList);
  615.                     }    /* (((TableEntryPtr)theEntry)->CollList != NULL) i.e. there's a collision list */
  616.                   else                         // this has no collision list
  617.                     {                         //clear this entry, and set Tag to indicate it's available
  618. /*
  619.                       for (i = 0; i < entrySize; i++, ((char  *)theEntry)++)
  620.                          *((Ptr)theEntry) = (char)0;
  621. */
  622.                       entryChars = theEntry;
  623.                       for (i = 0; i < entrySize; i++, entryChars++)
  624.                          *entryChars = (char)0;
  625.                       ((TableEntryPtr)theEntry)->Tag = kEmptySlot;
  626.                     }
  627.               }            /* (theHdl = NULL) i.e initial table entry */
  628.            else            // this is a list entry
  629.               {
  630.                  theHdlDeRefPtr = (TableEntryPtr)DEREF_OF(theHdl);
  631.                  if (preHdl == NULL)           //first list entry
  632.                     {                           //pesky - have to re-index initial table entry
  633.                        tblEntry = (HEntryPtr)PointInTable(Hash, Key, &dummy);
  634.                       ((TableEntryPtr)tblEntry)->CollList = theHdlDeRefPtr->CollList;
  635.                      }
  636.                  else                         // there are others in the list
  637.                    {
  638.                       preHdlDeRefPtr = (TableEntryPtr)DEREF_OF(preHdl);
  639.                       preHdlDeRefPtr->CollList = theHdlDeRefPtr->CollList;
  640.                       CLEAR_REF_OF(preHdl);
  641.                    }
  642. #if WINDOWS /*  11/6   RETAIN TILL DECIDE WHAT TO DO ABOUT SYSTEM HEAP */
  643.                    // don't want to us myGlobalFree if this is in the system heap
  644.                 if(InSys)
  645.                   {
  646.                     HUNLOCK(((TableEntryPtr)theEntry)->CollList);
  647.                     GlobalFree((HGLOBAL)((TableEntryPtr)theEntry)->CollList);
  648.                   }
  649.                 else
  650. #endif
  651.                  DISPOSEHANDLE (theHdl);
  652.               }            /* list entry */
  653.         else           // FindAnEntry failed
  654.            theReturn = ErrNotFound;
  655.  
  656.         return theReturn;
  657.    }        /* RemoveKeyEntry */
  658. // ---------------------------------------------------------------------------------
  659.  
  660.          /*
  661.             ReplaceEntry - Replace the fields of an existent entry OR add a new one.
  662.             ------------
  663.                Entry:    Hash        - the hash table to search
  664.                         Key            - Pointer to the Key to add.
  665.                         Value       - pointer to value to add.
  666.                         
  667.                Exit:    Returns ErrAlreadyExists if unable to replace or create a new one - unlikely.
  668.          */
  669.          
  670. OSErr  ReplaceEntry(HHand Hash, MemProcs MemHooks,KeyPtr Key,HEntryPtr Value)
  671.    {
  672.         OSErr            theReturn;
  673.         TableEntryPtr    theEntry;
  674.         TableEntryHdl   NewEntryHdl;
  675.         TableEntryHdl    * OldCollLstPtr = NULL;
  676.         TableEntryHdl    preHdl, currHdl;
  677.         TableInfoPtr    tblDeRefPtr;
  678.         Boolean            InSys;
  679.  
  680.         theReturn =  FindAnEntry(Key, (HEntryPtr  *)&theEntry, Hash, &currHdl, &preHdl);
  681.                              //First, lock Hash, so theEntry will remain valid
  682.         HLOCK(Hash);
  683.         tblDeRefPtr = (TableInfoPtr)DEREF_OF (Hash);
  684.         
  685.         if (theReturn == kNoSlot)        // Must create a new entry
  686.            { 
  687.               InSys = tblDeRefPtr->InSysHeap;
  688. /*  11/6   RETAIN TILL DECIDE WHAT TO DO ABOUT SYSTEM HEAP */
  689.               if(InSys)
  690.                   NewEntryHdl = (TableEntryHdl)NEWHANDLESYS (tblDeRefPtr->HashEntrySize);
  691.               else
  692.                 NewEntryHdl = (TableEntryHdl)NEWHANDLE (tblDeRefPtr->HashEntrySize);
  693.               if (NewEntryHdl == NULL)
  694.                   theReturn = memFullErr;
  695.                else
  696.                  {         //retain a ptr to CollList field, for linking new entry into head of list
  697.                    OldCollLstPtr = &theEntry->CollList;
  698.                    theEntry = (TableEntryPtr)DEREF_OF(NewEntryHdl);
  699.                   }
  700.            }    /* Creating a new entry */
  701.          if (theReturn != memFullErr)           /* Move the data in */
  702.            {
  703.               theEntry->Tag = InLineHash(Key);    // compute the hash value for the key.
  704.               (*(KeyRecPtr)&theEntry->theKey).firstKey  = ((KeyRecPtr)Key)->firstKey;
  705.               (*(KeyRecPtr)&theEntry->theKey).secondKey = ((KeyRecPtr)Key)->secondKey;
  706.  
  707.               memcpy(((Ptr)theEntry)+tblDeRefPtr->HValueOffset, Value, tblDeRefPtr->HashValueSize);
  708.  
  709.               if (OldCollLstPtr!= NULL)       //Added a new list item - hook it in at head of list
  710.                 {
  711.                     theEntry->CollList = *OldCollLstPtr;                  //point to previous head of list
  712.                     *OldCollLstPtr = NewEntryHdl;                         //hook in as new head of list
  713.                     CLEAR_REF_OF(NewEntryHdl);
  714.                  }
  715.               theReturn = noErr;
  716.               CLEAR_REF_OF(currHdl);
  717.            }        /* (theReturn != memFullErr) */
  718.         HUNLOCK(Hash);
  719.         return theReturn;
  720.    }    /* ReplaceEntry */
  721. // ---------------------------------------------------------------------------------
  722.  
  723.